Serving Online Requests with Mobile Servers

摘要

We study an online problem in which a set of mobile servers have to be movedin order to efficiently serve a set of requests that arrive in an onlinefashion. More formally, there is a set of $n$ nodes and a set of $k$ mobileservers that are placed at some of the nodes. Each node can potentially hostseveral servers and the servers can be moved between the nodes. There arerequests $1,2,\ldots$ that are adversarially issued at nodes one at a time. Anissued request at time $t$ needs to be served at all times $t' \geq t$. Thecost for serving the requests is a function of the number of servers andrequests at the different nodes. The requirements on how to serve the requestsare governed by two parameters $\alpha\geq 1$ and $\beta\geq 0$. An algorithmneeds to guarantee at all times that the total service cost remains within amultiplicative factor of $\alpha$ and an additive term $\beta$ of the currentoptimal service cost. We consider online algorithms for two differentminimization objectives. We first consider the natural problem of minimizingthe total number of server movements. We show that in this case for every $k$,the competitive ratio of every deterministic online algorithm needs to be atleast $\Omega(n)$. Given this negative result, we then extend the minimizationobjective to also include the current service cost. We give almost tight boundson the competitive ratio of the online problem where one needs to minimize thesum of the total number of movements and the current service cost. Inparticular, we show that at the cost of an additional additive term which isroughly linear in $k$, it is possible to achieve a multiplicative competitiveratio of $1+\varepsilon$ for every constant $\varepsilon>0$.